/**
 * Copyright ©2003~2019年1月29日 szkingdom
 * @author raohj
 * @date 2019年1月29日
 * @file RStraightSort.java
 * @comment : please input your comment to this file
 * @version : input version
 * @modify:
 * 		1、 2019年1月29日 由 raohj 新建文件
 */
package com.ccnu.demojava.algorithm;

import java.util.Random;

/**
 * @author raohj
 * @date 2019年1月29日
 * @version
 * @comment 数据结构与算法
 */
public class RSort {
	
	public static int quickSortCycles = 0;
	/**
	 * @author raohj
	 * @date 2019年1月29日
	 * @comment 直接插入排序。 基本思路为：假设i-1个元素是有序的，
	 *          通过逐个对比后面i个元素与(1~i-1)之间的大小，并将i插入只有序数组（i~i-1）中，形成有序数组(1~i)
	 *          因此算法可以简化为假设第一个元素是有序的. 时间复杂度为O(n²)
	 * @param
	 * @return
	 * @param datas
	 */
	public static void straightSort(int[] datas) {
		int len = datas.length;
		int sentry = 0;
		int j = 0;
		long cycles = 0;
		// 右半边无序数组
		for (int i = 1; i < len; i++) {
			cycles++;
			if (datas[i] < datas[i - 1]) {
				cycles++;
				sentry = datas[i];
				datas[i] = datas[i - 1];
				for (j = i - 2; j >= 0 && sentry < datas[j]; --j) {
					cycles++;
					datas[j + 1] = datas[j];
				}
				datas[j + 1] = sentry;
			}
		}
		System.out.println("straightSort算法处理[" + datas.length + "]条记录时，总的循环次数为[" + cycles + "]");
	}

	/**
	 * @author raohj
	 * @date 2019年1月29日
	 * @comment 直接插入排序的一种优化方法，主要优化后续移动查找
	 * @param
	 * @return
	 * @param datas
	 */
	public static void straightOfHalfSort(int[] datas) {
		int len = datas.length;
		int sentry = 0;
		long cycles = 0;
		int low, high, middle;
		// 右半边无序数组
		for (int i = 1; i < len; i++) {
			cycles++;
			if (datas[i] < datas[i - 1]) {
				cycles++;
				sentry = datas[i];
				datas[i] = datas[i - 1];
				low = 0;
				high = i - 2;
				while (low <= high) {
					cycles++;
					middle = (low + high) / 2;
					if (sentry < datas[middle]) {
						high = middle - 1;
					} else {
						low = middle + 1;
					}
				}
				if (high < 0) {
					high = 0;
					datas[high] = sentry;
				} else {
					System.arraycopy(datas, high, datas, high + 1, i - high - 1);
				}
			}
		}
		System.out.println("straightOfHalfSort算法处理[" + datas.length + "]条记录时，总的循环次数为[" + cycles + "]");
	}

	/**
	 * @author raohj
	 * @date 2019年1月29日
	 * @comment 冒泡排序法
	 * @param
	 * @return
	 * @param datas
	 */
	public static void bubbleSort(int[] datas) {
		int sentry = 0;
		long cycles = 0;
		for (int i = 0; i < datas.length; i++) {
			for (int j = i + 1; j < datas.length; j++) {
				cycles++;
				if (datas[i] > datas[j]) {
					sentry = datas[i];
					datas[i] = datas[j];
					datas[j] = sentry;
				}
			}
		}
		System.out.println("bubbleSort算法处理[" + datas.length + "]条记录时，总的循环次数为[" + cycles + "]");
	}

	/**
	 * @author raohj
	 * @date 2019年1月29日
	 * @comment 快速排序选择分区
	 * @param 
	 * @return 
	 * @param datas
	 * @param low
	 * @param high
	 * @return
	 */
	public static int Partition(int[] datas, int low, int high) {
		int sentry = datas[low];
		while (low < high) {
			quickSortCycles++;
			while(low < high && datas[high]>=sentry) {
				quickSortCycles++;
				high--;
			}
			datas[low] = datas[high];
			
			while(low < high && datas[low]<=sentry) {
				quickSortCycles++;
				low++;
			}
			datas[high] = datas[low];
		}
		datas[low] = sentry;
		return low;
	}

	/**
	 * @author raohj
	 * @date 2019年1月29日
	 * @comment 快速排序
	 * @param 
	 * @return 
	 * @param datas
	 * @param low
	 * @param high
	 */
	public static void quickSort(int[] datas, int low, int high) {
		if (low < high) {
			int pivotloc = Partition(datas, low, high);
			quickSort(datas, low, pivotloc - 1);
			quickSort(datas, pivotloc + 1, high);
		}
	}
	
	/**
	 * @author raohj
	 * @date 2019年1月29日
	 * @comment 简单选择排序
	 * @param 
	 * @return 
	 * @param datas
	 */
	public static void simpleSelectSort(int[] datas) {
		int sentry = 0;
		int tmp = 0;
		long cycles = 0;
		for(int i=0; i<datas.length; i++) {
			cycles++;
			sentry = i;
			for(int j=i; j<datas.length; j++) {
				cycles++;
				if(datas[j] < datas[sentry]) {
					sentry = j;
				}
			}
			tmp = datas[i];
			datas[i] = datas[sentry];
			datas[sentry] = tmp;
		}
		System.out.println("simpleSelectSort算法处理[" + datas.length + "]条记录时，总的循环次数为[" + cycles + "]");
	}

	/**
	 * @author raohj
	 * @date 2019年1月29日
	 * @comment 检验排序算法是否成功
	 * @param
	 * @return
	 * @param datas
	 */
	public static void testSort(int[] datas) {
		for (int i = 0; i < datas.length - 1; i++) {
			for (int j = i + 1; j < datas.length; j++) {
				if (datas[i] > datas[j]) {
					System.out.print("排序算法出错");
					return;
				}
			}
		}
		System.out.println("排序算法成功");
	}

	/**
	 * @author raohj
	 * @date 2019年1月29日
	 * @comment 测试基本算法
	 * @param
	 * @return
	 */
	public static void testAlgorithm() {
		int MAX_ARRAY = 100000;
		int[] datas = new int[MAX_ARRAY];
		Random rdm = new Random(1000000);
		for (int i = 0; i < datas.length; i++) {
			datas[i] = rdm.nextInt();
		}

		int[] copy1Datas = new int[datas.length];
		System.arraycopy(datas, 0, copy1Datas, 0, datas.length);

		int[] copy2Datas = new int[datas.length];
		System.arraycopy(datas, 0, copy2Datas, 0, datas.length);
		
		int[] copy3Datas = new int[datas.length];
		System.arraycopy(datas, 0, copy3Datas, 0, datas.length);
		
		int[] copy4Datas = new int[datas.length];
		System.arraycopy(datas, 0, copy4Datas, 0, datas.length);

		straightSort(datas);
		System.out.print("检测straightSort排序算法结果:");
		testSort(datas);

		System.out.println("=================================================================");
		System.out.println("检测straightSort处理有序数组时的情况");
		straightSort(datas);
		System.out.print("检测straightSort排序算法结果:");
		testSort(datas);

		System.out.println("=================================================================");
		straightOfHalfSort(copy1Datas);
		System.out.print("检测straightOfHalfSort排序算法结果:");
		testSort(copy1Datas);

		System.out.println("=================================================================");
		bubbleSort(copy2Datas);
		System.out.print("检测bubbleSort排序算法结果:");
		testSort(copy2Datas);
		
		System.out.println("=================================================================");
		quickSort(copy3Datas, 0, copy3Datas.length-1);
		System.out.println("quickSort算法处理[" + copy3Datas.length + "]条记录时，总的循环次数为[" + quickSortCycles + "]");
		System.out.print("检测quickSort排序算法结果:");
		testSort(copy3Datas);
		
		System.out.println("=================================================================");
		simpleSelectSort(copy4Datas);
		System.out.print("检测simpleSelectSort排序算法结果:");
		testSort(copy4Datas);
	}
}
